package com.origin.niuke.tree;

import general_class.TreeNode;

/**
 * NC162 二叉树中和为某一值的路径(三)
 * 算法：树
 * 两次深度优先搜索
 *
 * @author yezh
 * @date 2022/12/20 20:49
 */
public class NC162 {

    int ans = 0;
    public int FindPath (TreeNode root, int sum) {
        if (root == null) return ans;
        dfs(root, sum);
        FindPath(root.left, sum);
        FindPath(root.right, sum);
        return ans;
    }

    void dfs(TreeNode node, int sum) {
        if (node == null) return;
        // 不能通过等于 0 来判断, 因为 sum 即使到 0 了, 也还要递归, 因为有负数
        if (node.val == sum) ++ans;
        dfs(node.left, sum - node.val);
        dfs(node.right, sum - node.val);
    }

}
